package com.zhy.algorithm;


/**
 * @author 随缘而愈
 * @version 1.0
 * @description 二分法
 * @date 19/3/2024 下午7:00
 */
public class BinarySearch {
    public static int binarySearch(String[] sortedArray, String target) {
        int left = 0;
        int right = sortedArray.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 如果找到目标值，返回其索引  
            if (sortedArray[mid].equals(target)) {
                return mid;
            }

            // 如果目标值小于中间值，搜索左半部分  
            else if (sortedArray[mid].compareTo(target) > 0) {
                right = mid - 1;
            }

            // 如果目标值大于中间值，搜索右半部分  
            else {
                left = mid + 1;
            }
        }

        // 如果循环结束还没有找到目标值，返回-1  
        return -1;
    }

    // 测试上述代码
    public static void main(String[] args) {
        String[] sortedNames = {
                "Alice", "Bob", "Zhang", "David", "Wang", "Frank", "Liu",
                // ... 省略其他名字以确保列表长度为128
                "Xavier", "Yvonne", "zhao"
        };

        String targetName = "David"; // 要查找的名字  
        int index = binarySearch(sortedNames, targetName);

        if (index != -1) {
            System.out.println("找到名字 " + targetName + " 在索引 " + index);
        } else {
            System.out.println("名字 " + targetName + " 不在列表中");
        }
    }
}